package test0ne;

import java.util.*;

public class PassSF {

    public static List<TreeNode> findDuplicateSubtrees(TreeNode root) {
        List<TreeNode> result = new ArrayList<>();
        HashMap<String, Integer> treeMap = new HashMap<>();
        traverse(root, treeMap, result);
        return result;
    }

    public static String traverse(TreeNode root, HashMap<String, Integer> treeMap, List<TreeNode> result) {
        if(root == null) {
            return "#";
        }

        String thisTree = root.val + "," + traverse(root.left, treeMap, result) + traverse(root.right, treeMap, result);
        if(treeMap.get(thisTree) == null) {
            treeMap.put(thisTree, 1);
        }else if(treeMap.get(thisTree) == 1){
            result.add(root);
            treeMap.put(thisTree, treeMap.get(thisTree)+1);
        }
        return thisTree;
    }


    //给定二叉搜索树， 和数k，找出第k小的数
    public static int kthSmallest(TreeNode root, int k) {
        List<Integer> inOrder = new ArrayList<>();
        inOrder(root, inOrder);
        return inOrder.get(k-1);
    }

    private static void inOrder(TreeNode root, List<Integer> inOrder) {
        inOrder(root.left, inOrder);
        inOrder.add(root.val);
        inOrder(root.right, inOrder);
    }


    public static void main(String[] args) {
        TreeNode root = new TreeNode(1);
        root.left = new TreeNode(2);
        root.right = new TreeNode(3);

        root.left.left = new TreeNode(4);
        root.right.left = new TreeNode(2);
        root.right.right = new TreeNode(4);

        root.right.left.left = new TreeNode(4);

        findDuplicateSubtrees(root);
    }

}
